package com.up.interview.dataStructuresAndAlgorithms.find;

/**
 * @author: liuchengjun
 * @title: Find
 * @projectName: 海联技术中台V2.0
 * @depart 软件事业部
 * @description:
 * @date: 2025/10/28/周二 9:44 (星期二)
 * @since V2.0
 */
public class Find {


    public static void main(String[] args) {
        Integer[] arr = {0,1,16,24,35,47,59,62,73,88,99};
        boolean b = twoFind(arr, 16);
        System.out.println(b);
    }

    /**
     * 二分查找：有序数据寻找节点
     * - 取中位数，大则移动右，小则移动左
     * @param target
     * @param key
     * @return
     */
    public static boolean twoFind(Integer[] target,Integer key){
        int high = target.length -1;
        int low = 0;
        int i =0;
        while (low <= high){
            System.out.println(++i);
            int mid = (low + high)/2;
            if (target[mid] <key){
                low++;
            } else if (target[mid] > key) {
                high--;
            }else {
                return true;
            }
        }
        return false;
    }

    /**
     * 插入查找：核心公式  适合分布均匀
     * @param target
     * @param key
     * @return
     */
    public static boolean twoFind2(Integer[] target,Integer key){
        int high = target.length -1;
        int low = 0;
        int i =0;
        while (low <= high){
            System.out.println(++i);
            int mid = low+((key-target[low])*(high-low)/(target[high]-target[low]));
            if (target[mid] <key){
                low++;
            } else if (target[mid] > key) {
                high--;
            }else {
                return true;
            }
        }
        return false;
    }
}
